A major stumbling block to common use of digitized images is their size. An 8.5.times.11 image at 300 dots per inch (dpi) contains roughly 8,000,000 pixels. Even after binarization of a scanned image reduces the number of bits per pixel to 1, this is still 1 megabyte. Compression techniques are typically characterized as LOSSLESS or LOSSY. In LOSSLESS compression, no data is lost in the compression and subsequent decompression. In LOSSY compression, a certain amount of data is lost but it is acceptable since the essence of the compressed data is retained after decompression.
Common LOSSLESS compression techniques for binary images, like CCITT Group 3 or Group 4 or MMR can compress a binary image by factors of 10 to 20. This is still large when compared to the synthetic electronic form used to create a comparable image. Moreover, such compression techniques do not perform well for dithered images. This is because such compression techniques generally depend on the compressor's ability to predict the value of a pixel given neighboring pixels. Dithered images contain many very tiny dots which are intentionally arranged in a pseudo-random pattern. In these images, it is quite difficult to predict the value of a pixel, thus such compression techniques perform poorly.
Vector Quantization is another LOSSY based method for image compression that is well known. A vector quantizer (VQ) is a quantizer that maps k-dimensional input vectors into one of a finite set of k-dimensional reproduction vectors, or codewords. For image compression the input vector is a fixed grouping of pixels. A VQ can be divided into two parts: an encoder and a decoder. The encoder maps the input vector into a binary code representing the index of the selected reproduction vector, and the decoder maps the binary code into the selected reproduction vector. The reproduction vector becomes the decompressed value of the input vector.
Typically the decoder operates using a simple lookup table. To obtain acceptable results upon decompression, the number of reproduction vectors, and resulting lookup table, can be quite large. As the lookup table may be part of the compressed data stream, a large lookup table is undesirable.
Vector quantization is conceptually similar to a known method for performing compression on text images by grouping the symbols found into equivalence classes. In this method, symbols are extracted from the binary image and matched to templates for one or more equivalence classes. In order to get good compression, a classifier should operate with a small number of classes.
An example of image compression based on symbol matching is described in co-pending U.S. patent application Ser. No. 08/575,305 filed Dec. 20, 1995, entitled "Classification Of Scanned Symbols Into Equivalence Classes". A further example of image compression based on symbol matching is described in U.S. Pat. No. 5,303,313 entitled "Method and Apparatus For Compression Of Images", Mark et al., issued Apr. 12, 1994 (the '313 patent). In the '313 patent an image is "precompressed" prior to symbol matching. The '313 patent describes using run-length encoding for such precompression. Symbols are extracted from the run-length representation. A voting scheme is used in conjunction with a plurality of similarity tests to improve symbol matching accuracy. The '313 patent further discloses a template composition scheme wherein the template may be modified based on symbol matches.
However, the aforementioned symbol based compression techniques do not compress particularly well with respect to pictorial images, in particular dithered images. This is because the pseudo random patterns typically causes a high number of equivalence classes to be created and because a very large number of symbols must be classified (often each dot would be interpreted as a separate symbol).